package com.datastructure.test.closestsumofthree;

import java.util.ArrayList;
import java.util.Arrays;

public class ClosestSumOfThree {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        int[] nums = {-1,2,1,-4};
        ClosestSumOfThree closestSumOfThree = new ClosestSumOfThree();
        int closestSum = closestSumOfThree.ClosestSum(nums, 1);
        System.out.println(closestSum);
    }

    public int ClosestSum (int[] nums, int target) {
        // write code here
        combination(nums);
        int sum;
        int result = 0;
        int min = Integer.MAX_VALUE;
        for (ArrayList<Integer> list : res) {
            sum=0;
            for (Integer integer : list) {
                sum+=integer;
            }
            if(Math.abs(sum-target)<min){
                min=Math.abs(sum-target);
                result=sum;
            }
        }
        return result;
    }

    public void combination(int[] num) {
        // 1.排序
        Arrays.sort(num);
        dfs(num, 0, new ArrayList<>());
    }

    public void dfs(int[] num, int start, ArrayList<Integer> list){
        if(list.size()==3){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=start;i<num.length;i++){
            // 去重
            list.add(num[i]);
            // dfs传递下去的数值是 target-num[i]
            dfs(num, i+1, list);
            list.remove(list.size()-1);
        }
    }
}
